package com.zdp.leetcodeMiddle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/*
* 题目描述：
* 给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
提示：
intervals[i][0] <= intervals[i][1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 合并区间_56 {
    public static void main(String[] args) {
        合并区间_56 demo = new 合并区间_56();
        int[][] merge = demo.merge(new int[][]{
                {1, 3},
                {2, 6},
                {8, 10},
                {15, 18}
        });
        for(int[] temp1 : merge){
            for(int temp:temp1){
                System.out.print(temp+"\t");
            }
            System.out.println();
        }
    }

    /*
    * 解题思路：一下子就想到了哈夫曼编码
    * 保证 interval[i][0] < intervals[i+1][0]
    * 也就是说 按左边界 升序排序 intervals数组
    * 保证了可以合并区间 都是连续的
    * 如何合并？ 就是利用哈夫曼编码的那个思想，将可以合并的区间 放到result 中，
    * 然后将result 中的 区间与 intervals中的区间 进行比较合并
    * */
    public int[][] merge(int[][] intervals) {
        /*
        * 先对 intervals 以数组的左端点做升序排序
        * */
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] first, int[] second) {
                /*
                * 返回 1 说明 first>second
                * 0 等于
                * -1 first < second
                * */
                return first[0]-second[0];
            }
        });
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]);
        int j=0;
        for(int i=1;i<intervals.length;i++){
            int left = result.get(j)[0];
            int right = result.get(j)[1];
            int left1 = intervals[i][0];
            int right1 = intervals[i][1];
            // 判断是否重叠，如果重叠，就更新result中的数组，如果不重叠
            // 就将 intervals 数组中的数组加入到result
            if(right>=left1){
                // 重叠，生成新数组并更新
                int[] temp = new int[]{left,Math.max(right,right1)};
                result.remove(j);
                result.add(temp);
            }else{
                // 不重叠
                result.add(intervals[i]);
                j++;
            }
        }
        return result.toArray(new int[][]{});
    }
}
